Ngôn ngữ L nằm trong BPP nếu tồn tại máy Turing ngẫu nhiên M thỏa mãn

• M chạy trong thời gian đa thức
• Với mọi x trong L, M trả lời 1 với xác suất ít nhất 2/3
• Với mọi x không trong L, M trả lời 1 với xác suất không quá 1/3

Không như lớp ZPP, máy M bắt buộc phải chạy trong thời gian đa thức, bất kể các lựa chọn ngẫu nhiên là thế nào.

Ngoài ra, BPP cũng có thể được định nghĩa bằng máy Turing đơn định. Ngôn ngữ L nằm trong BPP nếu tồn tại đa thức p và máy Turing đơn định M, sao cho

• M chạy trong thời gian đa thức
• Với mọi x trong L, tỉ lệ số xâu y độ dài p(|x|) thỏa mãn M(x,y) = 1 là ít nhất 2/3
• Với mọi x không trong L, tỉ lệ số xâu y độ dài p(|x|) thỏa mãn M(x,y) = 1 là không quá 1/3

Trong định nghĩa thứ hai, y tương ứng với các lựa chọn ngẫu nhiên của thuật toán.